package com.sicheng.蓝桥.省赛.第九届;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/1/27 13:25
 */
public class 耐摔指数 {
   public static int getMinSteps(int num, int floorNum) {
        if (num < 1 || floorNum < 1)
            return 0;

        // 备忘录，存储num个手机，floorNum层楼条件下的最优化尝试次数
        int[][] cache = new int[num + 1][floorNum + 1];
        // 把备忘录每个元素初始化成最大的尝试次数
        for (int i = 1; i <= num; i++)
            for (int j = 1; j <= floorNum; j++)
                cache[i][j] = j;

        for (int n = 2; n <= num; n++)
            for (int m = 1; m <= floorNum; m++)
                for (int k = 1; k < m; k++)
                    // 扔手机的楼层从1到m枚举一遍，如果当前算出的尝试次数小于上一次算出的尝试次数，则取代上一次的尝试次数。
                    cache[n][m] = Math.min(cache[n][m], 1 + Math.max(cache[n - 1][k - 1], cache[n][m - k]));

        return cache[num][floorNum];
    }

    public static void main(String[] args) {

        long s = System.nanoTime();
        System.out.println(getMinSteps(3, 100000));
        long e = System.nanoTime();
        System.out.println(e-s);
    }
}
